The object of the present invention is a cryptography method of the so-called public key type based on the discrete logarithm using the calculation of a modulo p quantity.
It finds an application in the generation of digital message signatures, in an authentication session between two entities or in the encoding of data.
In such procedures, security is based on the extreme difficulty that there is in reversing certain functions and particularly the discrete logarithm.
This problem consists, given the mathematical relationship y=gx modulo p, which will be denoted hereinafter y=gxmodp (which means y is the remainder of the division of gx by p), of finding x when p, g and y are known. This problem is impossible to resolve, in the current state of knowledge, as soon as the size of p reaches or exceeds 512 bits and the size of x reaches or exceeds 128 bits.
In such systems, there is in general an authority which supplies the number p of large size, constituting the modulus. The authority also chooses an integer g, referred to as the base, such that the set generated by g, i.e. the set formed by the numbers gxmodp) for x belonging to the interval [0, p-1], is a subset of maximum size, at least 2128.
The parameters p and g are said to be xe2x80x9cpublicxe2x80x9d, i.e. they are supplied by the authority to all the users attached to this authority.
According to certain variants, these parameters are chosen individually by each user and, in this case, form an integral part of its public key.
A major drawback of the use of cryptographic systems lies in the need to have relatively large calculation and storage means because of the complex calculations which are performed.
This is because the calculation of the quantity gkmodp consists in performing modular multiplications and this is expensive in calculation time and memory space. In simple electronic devices using only standard microprocessors, this type of operation can scarcely be performed.
For electronic devices having a specialised processor for this type of calculation, it is in spite of everything desirable to limit the calculation time and memory space necessary for the intermediate results.
This is because calculating the quantity gkmodp is in general relatively expensive using the conventional method of xe2x80x9csquare-multiplyxe2x80x9d, known by the English abbreviation SQM, since it is equivalent on average to 3/2 Log2(p) multiplications.
According to this method all the powers of g are calculated, i.e. all the squares: g0, g1, g2 . . . gn, when k is n bits long, since the required multiplications between these powers are performed (for example g17=g1xc2x7g16)
According to the simple xe2x80x9csquare-multiplyxe2x80x9d method, gk requires n/2 multiplications and n squares.
Where N signatures are to be supplied on a single occasion, Ngk is produced, and then a parallel calculation is performed.
The parallel xe2x80x9csquare-multiplyxe2x80x9d method requires Nxc3x97n/2 multiplications and n squares.
A method proposed by E. BRICKEL et al, referred to by the abbreviation BGKW, makes it possible to reduce the number of multiplications in the case of the square-multiply method but introduces a requirement to store numerous precalculated constants and therefore the need to have a highly disadvantageous quantity of storage memories.
Introducing a parallel calculation of N values into this method entails the use of numerous registers for keeping the intermediate results.
This method therefore becomes much more constraining when there is a situation where it is a case of generating a large number of signatures in a very short time since in this case parallel calculation is introduced.
The object of the present invention is to remedy all these drawbacks. It affords a solution, flexible and inexpensive in calculation time and memory space, to the implementation of cryptographic algorithms for all cryptography systems and in particular by means of portable appliances of the microprocessor chip card type.
According to a first object of the invention, the proposed cryptography method reduces the number of modular multiplications so that savings in calculation times are obtained of 15 to 40% and more depending on the cryptography schemes used (Schnorr or El Gamal).
According to the invention, two solutions are proposed in order to reduce the number of multiplications, one consisting of generating xe2x80x9chollowxe2x80x9d exponents k with few bits at 1, but of sufficient length to keep all the security for the system, and the other consisting in performing the calculations of the powers of g in parallel whilst combining the exponents with each other so as not to perform the same power calculation twice for a given exponent.
An object of the invention is more particularly a public key cryptography method based on the discrete logarithm using the calculation of the quantity qkmodp where p is a prime number referred to as the modulus, k a random number normally of length n bits and g an integer referred to as the base, in which an entity E performs authentication and/or signature and/or encoding operations, comprising exchanges of signals with another entity in which this quantity acts, characterised in that it includes the following steps for the entity:
generating a random exponent k of length N bits, N being equal to n+b bits,
calculating the Hamming weighting C of this exponent and comparing it with a value h fixed in advance,
checking whether the random value k fulfils the condition Cxe2x89xa7h
rejecting the random value k where the Hamming weighting is less than h and recommencing the generation of new exponents until an exponent satisfying this condition is obtained,
or keeping this value in the contrary case,
calculating the expression gkmodp from the kept value,
using this expression in an exchange of electronic signals with the other entity.
Another object of the invention is a public-key cryptography method based on the discrete logarithm using the calculation of the quantity gkmodp where p is a prime number referred to as the modulus, k a random number normally of length n bits and g an integer referred to as the base, in which an entity E performs authentication and/or signature and/or encoding operations, comprising exchanges of signals with another entity in which several quantities of this type act, characterised in that it includes the following steps for the entity:
generating a set of random exponents kj of n bits of weighting ai expressed by the expression:
kj=xcexa3ai2i
calculating in parallel the powers of g2i whilst combining the exponents so that the powers of g already calculated for an exponent serve for other exponents in which they act,
for each given kj, calculating the powers of g not yet calculated and grouping together all these powers in order to obtain the required expression gkjmodp,
using these expressions in an exchange of signals with the other entity.
According to a first embodiment, these steps of calculating in parallel and grouping together include the following operations:
combining the exponents in pairs in order to obtain exponents kc which are a reflection of their common parts and reiterating the combinations on the combination result obtained,
calculating quantities Gkc for each value of kc such that:
xe2x80x83Gkc=gkcmodp
combining an exponent kj with the exponent kc obtained for the combination to which this exponent belongs so as to eliminate the common parts and keep only the different parts,
defining exponents kxe2x80x2j which are a reflection of the different parts between a given exponent kj and a given exponent kc,
calculating quantities Gkxe2x80x2j such that:
Gkxe2x80x2j=gkxe2x80x2jmodp
determining the expressions Gkjmodp by performing multiplications between the quantities Gkc obtained at each iteration.
In a second embodiment, the steps of calculating in parallel and grouping together include the following operations:
combining the exponents together so as to form all the subsets of possible combinations of exponents having common parts,
defining exponents kc which are a reflection of the common parts, for each subset of combinations such that the non-nil bits of given weighting correspond to the non-nil bits of the same weighting of the combination under consideration,
calculating quantities Gkc for each value of kc such that: Gkc=gkcmodp
combining each exponent kj with all the exponents kc obtained for each subset of combinations to which this exponent kj belongs so as to eliminate the common parts and keep only the different parts,
defining exponents kxe2x80x2j which are a reflection of different parts between a given exponent kj and a given exponent kc,
calculating quantities Gkxe2x80x2j such that:
Gkxe2x80x2j=gkxe2x80x2jmodp
determining the expressions gkjmodp by performing a multiplication between the quantities Gxe2x80x2kj and Gko for each kj.
According to another object of the invention, the combinations making it possible to obtain the common parts between the exponents are made by AND logic functions.
According to another object of the invention, the combinations for obtaining the different parts are effected by exclusive-OR logic functions.